package com.jhy.review.paixu;

import java.util.Arrays;

/**
 * @author go_jhy
 * @create 2022/6/13 - 上午 9:40
 * 堆排序
 * 时间复杂度是n*logn 空间复杂度 是 1  看一眼的时间复杂度是1
 */
public class Code03_HeapSort {
    public static void heapSort(int[] arr) {
        if (arr != null && arr.length < 2) {
            return;
        }

//        //变成一个堆结构 往上面变成一个大根堆，0的位置一定是最大的数
//        for (int i = 0; i < arr.length; i++) {
//            heapInsert(arr, i);
//        }


        //更快的一种方式 heapify 操作 时间复杂度是n
        for (int j = arr.length-1;j >= 0;j--){
            heapify(arr,j,arr.length);

        }

        // 记录数组的长度,当前的实际长度
        int helpsize = arr.length;
        // 将最后一个数删除，并且和第一个数的进行交换
        swap(arr, 0, --helpsize);
        // 然后进行heapify，从上往下变成一个大根堆
        while (helpsize > 0) {
            heapify(arr, 0, helpsize);
            //再一次进行交换 也就是最后一个数已经是最大的了 排序好了
            swap(arr, 0, --helpsize);
        }
    }

    private static void heapify(int[] arr, int index, int helpsize) {
        //判断当前坐标是否还有左孩子 ，因为左孩子没有了话 那么右孩子也就没有了
        int left = (2 * index) + 1;
        //作为判断循环的条件
        while (left < helpsize) {
            //将左右孩子的坐标 哪个比较大的，就记录起来
            int largest = left + 1 < helpsize && arr[left + 1] > arr[left] ? left + 1 : left;
            //然后刚刚记录的这个最大的下标的值和传入的下标做比较
            largest = arr[index] > arr[largest] ? index : largest;

            //那么现在index就是最大的那个,就直接结束本次循环
            if(largest == index){
                break;
            }
            //如果largest是左右孩子大的那个 就和index的值就和左右孩子那个大的值进行交换
            swap(arr,index,largest);
            //然后index现在就是之前largest的位置，继续往下判断
            index = largest;
            left = (2 * index) + 1;
        }
    }


    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 2, 6, 7, 1, 9};
        heapSort(arr);
        System.out.println(arr.length);
        System.out.println(Arrays.toString(arr));
    }


}
